package com.sakura.二叉树;

public class Code662_二叉树最大宽度 {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static final int MAX_LEN = 3001;

    // 存储节点的数组
    public static TreeNode[] rQ = new TreeNode[MAX_LEN];
    // 记录节点的编号
    public static int[] iQ = new int[MAX_LEN];

    public static int l, r;

    public int widthOfBinaryTree(TreeNode root) {
        int ans = 0;
        if (root != null) {
            l = r = 0;
            rQ[r] = root;
            iQ[r++] = 1;
            while (l < r) {
                int size = r - l;
                ans = Math.max(ans, iQ[r - 1] - iQ[l] + 1);
                for (int i = 0; i < size; i++) {
                    TreeNode cur = rQ[l];
                    int id = iQ[l++];
                    if (cur.left != null) {
                        rQ[r] = cur.left;
                        iQ[r++] = id * 2;
                    }
                    if (cur.right != null) {
                        rQ[r] = cur.right;
                        iQ[r++] = id * 2 + 1;
                    }
                }
            }
        }
        return ans;
    }
}
